{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #积木拼接"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #backtracking #matrix"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #回溯 #矩阵"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: composeCube"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #积木拼接"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "欢迎各位勇者来到力扣城，本次试炼主题为「积木拼接」。\n",
    "勇者面前有 `6` 片积木（厚度均为 1），每片积木的形状记录于二维字符串数组 `shapes` 中，`shapes[i]` 表示第 `i` 片积木，其中 `1` 表示积木对应位置无空缺，`0` 表示积木对应位置有空缺。\n",
    "例如 `[\"010\",\"111\",\"010\"]` 对应积木形状为\n",
    "![image.png](https://pic.leetcode-cn.com/1616125620-nXMCxX-image.png)\n",
    "\n",
    "拼接积木的规则如下：\n",
    "- 积木片可以旋转、翻面\n",
    "- 积木片边缘必须完全吻合才能拼接在一起\n",
    "- **每片积木片 `shapes[i]` 的中心点在拼接时必须处于正方体对应面的中心点**\n",
    "\n",
    "例如 `3*3`、`4*4` 的积木片的中心点如图所示（红色点）：\n",
    "![middle_img_v2_c2d91eb5-9beb-4c06-9726-f7dae149d86g.png](https://pic.leetcode-cn.com/1650509082-wObiEp-middle_img_v2_c2d91eb5-9beb-4c06-9726-f7dae149d86g.png){:height=\"150px\"}\n",
    "\n",
    "\n",
    "请返回这 6 片积木能否拼接成一个**严丝合缝的正方体**且每片积木正好对应正方体的一个面。\n",
    "\n",
    "**注意：**\n",
    "- 输入确保每片积木均无空心情况（即输入数据保证对于大小 `N*N` 的 `shapes[i]`，内部的 `(N-2)*(N-2)` 的区域必然均为 1）\n",
    "- 输入确保每片积木的所有 `1` 位置均连通\n",
    "\n",
    "**示例 1：**\n",
    ">输入：`shapes = [[\"000\",\"110\",\"000\"],[\"110\",\"011\",\"000\"],[\"110\",\"011\",\"110\"],[\"000\",\"010\",\"111\"],[\"011\",\"111\",\"011\"],[\"011\",\"010\",\"000\"]]`\n",
    ">\n",
    ">输出：`true`\n",
    ">\n",
    ">解释：\n",
    "![cube.gif](https://pic.leetcode-cn.com/1616125823-hkXAeN-cube.gif)\n",
    "\n",
    "**示例 2：**\n",
    ">输入：`shapes = [[\"101\",\"111\",\"000\"],[\"000\",\"010\",\"111\"],[\"010\",\"011\",\"000\"],[\"010\",\"111\",\"010\"],[\"101\",\"111\",\"010\"],[\"000\",\"010\",\"011\"]]`\n",
    ">\n",
    ">输出：`false`\n",
    ">\n",
    ">解释： \n",
    ">由于每片积木片的中心点在拼接时必须处于正方体对应面的中心点，积木片 `[\"010\",\"011\",\"000\"]` 不能作为 `[\"100\",\"110\",\"000\"]` 使用，因此无法构成正方体\n",
    "\n",
    "\n",
    "**提示：**\n",
    "- `shapes.length == 6`\n",
    "- `shapes[i].length == shapes[j].length`\n",
    "- `shapes[i].length == shapes[i][j].length`\n",
    "- `3 <= shapes[i].length <= 10`\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [De4qBB](https://leetcode.cn/problems/De4qBB/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [De4qBB](https://leetcode.cn/problems/De4qBB/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[\"000\",\"110\",\"000\"],[\"110\",\"011\",\"000\"],[\"110\",\"011\",\"110\"],[\"000\",\"010\",\"111\"],[\"011\",\"111\",\"011\"],[\"011\",\"010\",\"000\"]]', '[[\"101\",\"111\",\"000\"],[\"000\",\"010\",\"111\"],[\"010\",\"011\",\"000\"],[\"010\",\"111\",\"010\"],[\"101\",\"111\",\"010\"],[\"000\",\"010\",\"011\"]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\tdef composeCube(self, shapes):\n",
    "\t\tn = len(shapes[0][0])\n",
    "\t\tself.mark1 = (1 << n) - 1\n",
    "\t\tself.mark2 = (1 << (n - 1)) - 1\n",
    "\t\tself.mark3 = self.mark2 - 1\n",
    "\t\tself.mark4 = 1 << (n - 1)\n",
    "\t\tself.bit = n\n",
    "\t\tn1 = 0 #顶点\n",
    "\t\tn2 = 0 #边上点\n",
    "\t\tn3 = 0 #面内点\n",
    "\t\tfor shape in shapes:\n",
    "\t\t\tfor i in range(n):\n",
    "\t\t\t\tfor j in range(n):\n",
    "\t\t\t\t\tif shape[i][j] == '1':\n",
    "\t\t\t\t\t\tif i in {0, n - 1} and j in {0, n - 1}:\n",
    "\t\t\t\t\t\t\tn1 += 1\n",
    "\t\t\t\t\t\telif i in {0, n - 1} or j in {0, n - 1}:\n",
    "\t\t\t\t\t\t\tn2 += 1\n",
    "\t\t\t\t\t\telse:\n",
    "\t\t\t\t\t\t\tn3 += 1\n",
    "\t\tif n1 != 8 or n2 != (n - 2) * 12 or n3 != (n - 2) * (n - 2) * 6:\n",
    "\t\t\treturn False\n",
    "\t\tmarks = [self.calc(shape) for shape in shapes]\n",
    "\t\treturn self.dfs(marks, 62, 0, [], []) #固定shapes[0]作底边, 其任何旋转/翻转都可以转化为原形状\n",
    "\t\n",
    "\tdef dfs(self, marks, mark, idx, edges, top): #底面&顶面按顺时针顺序, 竖直边按从下往上顺序\n",
    "\t\tif mark == 0:\n",
    "\t\t\treturn True\n",
    "\t\tfor i in range(1, 6):\n",
    "\t\t\tif mark >> i & 1 == 1:\n",
    "\t\t\t\tfor l, r, t in self.chk(marks[i], marks[0][idx - 4][0], edges, top):\n",
    "\t\t\t\t\tif idx == 0:\n",
    "\t\t\t\t\t\tedges.append(l)\n",
    "\t\t\t\t\tedges.append(r)\n",
    "\t\t\t\t\ttop.append(t)\n",
    "\t\t\t\t\tif self.dfs(marks, mark ^ 1 << i, idx + 1, edges, top):\n",
    "\t\t\t\t\t\treturn True\n",
    "\t\t\t\t\tif idx == 0:\n",
    "\t\t\t\t\t\tedges.pop()\n",
    "\t\t\t\t\tedges.pop()\n",
    "\t\t\t\t\ttop.pop()\n",
    "\t\treturn False\n",
    "\t\n",
    "\tdef chk(self, cur, bottom, edges, top):\n",
    "\t\tres = []\n",
    "\t\tfor b, l, r, t in set(cur):\n",
    "\t\t\tif len(top) < 4: #4个侧面\n",
    "\t\t\t\tr |= int(bottom & self.mark4 != 0) #在比较前计算底面影响, 保证最后一个侧面比较时逻辑一致\n",
    "\t\t\t\tif bottom & b != 0: #底部有重合, 包含两端\n",
    "\t\t\t\t\tcontinue\n",
    "\t\t\t\tif (bottom ^ b) & self.mark3 != self.mark3: #底部未填满, 不含两端\n",
    "\t\t\t\t\tcontinue\n",
    "\t\t\t\tif edges and l & edges[-1] != 0: #左侧棱有重合, 包含两端\n",
    "\t\t\t\t\tcontinue\n",
    "\t\t\t\tif edges and (edges[-1] ^ l) & self.mark2 != self.mark2: #左侧未填满, 不含上顶点\n",
    "\t\t\t\t\tcontinue\n",
    "\t\t\t\tif len(edges) == 4:\n",
    "\t\t\t\t\tif edges[0] & r != 0: #最后一个侧面与第一个侧面有重合, 包含两端\n",
    "\t\t\t\t\t\tcontinue\n",
    "\t\t\t\t\tif (edges[0] ^ r) & self.mark2 != self.mark2: #最后一个侧面与第一个侧面未填满, 不含上顶点\n",
    "\t\t\t\t\t\tcontinue\n",
    "\t\t\telse: #顶面\n",
    "\t\t\t\ttmp = [b, r, self.reverse(t), self.reverse(l)]\n",
    "\t\t\t\tvalid = True\n",
    "\t\t\t\tfor i in range(4):\n",
    "\t\t\t\t\tbit1 = 1 if top[i - 1] & self.mark4 != 0 else 0\n",
    "\t\t\t\t\tbit2 = self.mark4 if top[(i + 1) % 4] & 1 == 1 else 0\n",
    "\t\t\t\t\tif (top[i] | bit1 | bit2) ^ tmp[i] != self.mark1:\n",
    "\t\t\t\t\t\tvalid = False\n",
    "\t\t\t\t\t\tbreak\n",
    "\t\t\t\tif valid == False:\n",
    "\t\t\t\t\tcontinue\n",
    "\t\t\tres.append([l, r, t]) #l均只来自侧面, r包含底面对下顶点的影响\n",
    "\t\treturn res\n",
    "\t\t\n",
    "\tdef calc(self, shape):\n",
    "\t\tn = len(shape)\n",
    "\t\t#border1不翻转逆时针; border2上下翻转后逆时针\n",
    "\t\tborder1 = [list(shape[-1]), [shape[i][-1] for i in range(n - 1, -1, -1)], list(shape[0])[::-1], [shape[i][0] for i in range(n)]]\n",
    "\t\tborder2 = [list(shape[0]), [shape[i][-1] for i in range(n)], list(shape[-1])[::-1], [shape[i][0] for i in range(n - 1, -1, -1)]]\n",
    "\t\tbot = [self.toNum(x) for x in border1 + border2]\n",
    "\t\tleft = [self.toNum(border1[i - 1][::-1]) for i in range(4)] + [self.toNum(border2[i - 1][::-1]) for i in range(4)]\n",
    "\t\tright = [self.toNum(border1[(i + 1) % 4]) for i in range(4)] + [self.toNum(border2[(i + 1) % 4]) for i in range(4)]\n",
    "\t\ttop = [self.toNum(border1[i - 2][::-1]) for i in range(4)] + [self.toNum(border2[i - 2][::-1]) for i in range(4)]\n",
    "\t\treturn [(bot[i], left[i], right[i], top[i]) for i in range(8)]\n",
    "\t\n",
    "\tdef toNum(self, stack):\n",
    "\t\tres = 0\n",
    "\t\tfor i, c in enumerate(stack):\n",
    "\t\t\tres += int(c) << i\n",
    "\t\treturn res\n",
    "\t\n",
    "\tdef reverse(self, n): #left和top是反转后的值, 比较顶面时须要再反转\n",
    "\t\tres = 0\n",
    "\t\tfor i in range(self.bit):\n",
    "\t\t\tres |= (n >> i & 1) << (self.bit - i - 1)\n",
    "\t\treturn res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "def make_shapes(shapes):\n",
    "    n = len(shapes[0])\n",
    "    mat = [[[0] * n for _ in range(n)] for _ in range(6)]\n",
    "    for k in range(6):\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                c = shapes[k][i][j]\n",
    "                mat[k][i][j] = int(c)\n",
    "    return mat\n",
    "\n",
    "\n",
    "# 一片积木的合法性：除了外圈，都必须填满\n",
    "def valid_shape(shape):\n",
    "    n = len(shape)\n",
    "    for i in range(1, n - 1):\n",
    "        for j in range(1, n - 1):\n",
    "            if shape[i][j] == 0:\n",
    "                return False\n",
    "    return True\n",
    "\n",
    "\n",
    "def valid_shapes(shapes):\n",
    "    # 检查每一片\n",
    "    for i in range(6):\n",
    "        if not valid_shape(shapes[i]):\n",
    "            return False\n",
    "    return True\n",
    "\n",
    "\n",
    "class Area:\n",
    "    def __init__(self, mat):\n",
    "        self.mat = mat\n",
    "        self.n = len(mat)\n",
    "        self.edges = [None] * 4  # 左上右下4条棱，顺时针方向。\n",
    "        self.corners = [None] * 4  # 左上右下4条棱的起点。\n",
    "        self.make_edges()\n",
    "        self.make_corners()\n",
    "\n",
    "    def make_edges(self):\n",
    "        self.edges[0] = [self.mat[i][0] for i in range(self.n - 1, -1, -1)]\n",
    "        self.edges[1] = self.mat[0][::]\n",
    "        self.edges[2] = [self.mat[i][-1] for i in range(self.n)]\n",
    "        self.edges[3] = self.mat[-1][::-1]\n",
    "\n",
    "    def make_corners(self):\n",
    "        self.corners[0] = self.mat[-1][0]\n",
    "        self.corners[1] = self.mat[0][0]\n",
    "        self.corners[2] = self.mat[0][-1]\n",
    "        self.corners[3] = self.mat[-1][-1]\n",
    "\n",
    "    def cell_cnt_in_corners(self):\n",
    "        return sum(self.corners)\n",
    "\n",
    "    def cell_cnt_in_edges_without_corners(self):\n",
    "        cnt = 0\n",
    "        for edge in self.edges:\n",
    "            cnt += sum(edge)\n",
    "        cnt -= self.cell_cnt_in_corners() * 2\n",
    "        return cnt\n",
    "\n",
    "\n",
    "def valid_areas(areas):\n",
    "    # 角上砖块数目需要==8\n",
    "    corner_cell_cnt = 0\n",
    "    for area in areas:\n",
    "        cnt = area.cell_cnt_in_corners()\n",
    "        corner_cell_cnt += cnt\n",
    "    if corner_cell_cnt != 8:\n",
    "        return False\n",
    "    # 棱上（不包括角）上的砖块数目需要==12*(n-2)\n",
    "    n = areas[0].n\n",
    "    edge_cell_cnt = 0\n",
    "    for area in areas:\n",
    "        cnt = area.cell_cnt_in_edges_without_corners()\n",
    "        edge_cell_cnt += cnt\n",
    "    if edge_cell_cnt != 12 * (n - 2):\n",
    "        return False\n",
    "    return True\n",
    "\n",
    "\n",
    "# 返回merge_valids.\n",
    "# merge_valids[i][di][ri][j][dj][rj] 表示第i块板的di方向ri翻转，和第j块板的dj方向rj翻转，是否可以拼接。\n",
    "# i,j取值[0,6)，di,dj取值[0,4), ri,rj取值[0,2)\n",
    "def calc_merge_valids(areas):\n",
    "    merge_valids = [[[[[[False] * 2 for _ in range(4)] for _ in range(6)] for _ in range(2)] for _ in range(4)] for _ in range(6)]\n",
    "    for i in range(6):\n",
    "        for di in range(4):\n",
    "            for ri in range(2):\n",
    "                for j in range(6):\n",
    "                    if i == j:\n",
    "                        continue\n",
    "                    for dj in range(4):\n",
    "                        for rj in range(2):\n",
    "                            valid = calc_merge_valid(areas[i], di, ri, areas[j], dj, rj)\n",
    "                            merge_valids[i][di][ri][j][dj][rj] = valid\n",
    "    for i in range(6):\n",
    "        for di in range(4):\n",
    "            for ri in range(2):\n",
    "                for j in range(6):\n",
    "                    if i == j:\n",
    "                        continue\n",
    "                    for dj in range(4):\n",
    "                        for rj in range(2):\n",
    "                            assert merge_valids[i][di][ri][j][dj][rj] == merge_valids[j][dj][rj][i][di][ri]\n",
    "                            assert merge_valids[i][di][1 - ri][j][dj][rj] == merge_valids[j][dj][rj][i][di][1 - ri]\n",
    "    return merge_valids\n",
    "\n",
    "\n",
    "def calc_merge_valid(area0, d0, r0, area1, d1, r1):\n",
    "    edge0 = area0.edges[d0] if r0 == 0 else area0.edges[d0][::-1]  # 本板不动\n",
    "    edge1 = area1.edges[d1] if r1 == 1 else area1.edges[d1][::-1]  # 另板需要反过来对接\n",
    "    return can_join(edge0, edge1)\n",
    "\n",
    "\n",
    "def can_join(edge0, edge1):\n",
    "    n = len(edge0)\n",
    "    if edge0[0] + edge1[0] > 1 or edge0[-1] + edge1[-1] > 1:\n",
    "        return False\n",
    "    for i in range(1, n - 1):\n",
    "        if edge0[i] + edge1[i] != 1:\n",
    "            return False\n",
    "    return True\n",
    "\n",
    "\n",
    "# 每块积木的每条边至少有一个可以和别人拼\n",
    "def valid_merge_valids(merge_valids):\n",
    "    for i in range(6):\n",
    "        for di in range(4):\n",
    "            for ri in range(2):\n",
    "                valid_cnt = 0\n",
    "                for j in range(6):\n",
    "                    if i == j:\n",
    "                        continue\n",
    "                    for dj in range(4):\n",
    "                        for rj in range(2):\n",
    "                            valid_cnt += merge_valids[i][di][ri][j][dj][rj]\n",
    "                if valid_cnt == 0:\n",
    "                    return False\n",
    "    return True\n",
    "\n",
    "\n",
    "class Manager:\n",
    "    def __init__(self, merge_valids):\n",
    "        self.merge_valids = merge_valids\n",
    "        # states为最终摆放状态\n",
    "        # states[i]为第i个空间，放了什么。[i, di, ri]表示放了第i块板[0,6)，di旋转[0,4)，ri翻转[0,2)。\n",
    "        # states[0]为离我最近的正面立板。\n",
    "        # states[1]为左立板\n",
    "        # states[2]为上盖板\n",
    "        # states[3]为右立板\n",
    "        # states[4]为下底板\n",
    "        # states[5]为对面立板。\n",
    "        self.states = [[-1, -1, -1] for _ in range(6)]\n",
    "        # 12条棱的状态\n",
    "        self.edges = [[] for _ in range(12)]  # 每个棱空间中可以放置0个、1个、2个棱。每个棱以[i, di, ri]来描述。\n",
    "        # 面空间和棱空间的对应关系\n",
    "        self.space_edge = [[0, 1, 2, 3], [4, 5, 0, 6], [5, 7, 8, 1], [2, 8, 9, 10], [6, 3, 10, 11], [9, 7, 4, 11]]\n",
    "        self.space_edge_rev = [[0, 0, 0, 0], [0, 0, 1, 0], [1, 0, 0, 1], [1, 1, 0, 0], [1, 1, 1, 0], [1, 1, 1, 1]]  # 第一次出现，方向为0。第二次出现方向为1。\n",
    "\n",
    "    def merge_all(self):\n",
    "        # 放置第一块板\n",
    "        self.place(0, 0, 0, 0)  # 正面立板先确定放法。这个就固定了，不必旋转，也不必翻转。\n",
    "        areas = [1, 2, 3, 4, 5]  # 剩余的板\n",
    "        ans = self.try_merge(areas, 1)\n",
    "        return ans\n",
    "\n",
    "    # i: 第几块板 di：把板的第几个边对到当前的空间0位置 ri:是否翻转板\n",
    "    def place(self, space_id, i, di, ri):\n",
    "        edges = self.space_edge[space_id]\n",
    "        pos = [(0 + di) % 4, (1 + di) % 4, (2 + di) % 4, (3 + di) % 4]\n",
    "        if ri:\n",
    "            pos[1], pos[3] = pos[3], pos[1]\n",
    "        placed = []\n",
    "        for k in range(4):\n",
    "            edge_id = edges[k]\n",
    "            dk = pos[k]\n",
    "            edge = self.edges[edge_id]\n",
    "            if len(edge) == 1:\n",
    "                if not self.merge_valids[edge[0][0]][edge[0][1]][edge[0][2]][i][dk][ri]:\n",
    "                    break\n",
    "            placed.append(edge_id)\n",
    "            self.edges[edge_id].append((i, dk, ri))\n",
    "        return placed\n",
    "\n",
    "    def try_merge(self, areas, space_id):\n",
    "        if space_id == 6:\n",
    "            return True\n",
    "        for area_id in areas:\n",
    "            for d in range(4):\n",
    "                for r in range(2):\n",
    "                    placed = self.place(space_id, area_id, d, r)\n",
    "                    if len(placed) == 4:\n",
    "                        new_areas = [x for x in areas if x != area_id]\n",
    "                        ans = self.try_merge(new_areas, space_id + 1)\n",
    "                        if ans:\n",
    "                            return True\n",
    "                    for i in placed:\n",
    "                        self.edges[i].pop()\n",
    "        return False\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def composeCube(self, shapes: List[List[str]]) -> bool:\n",
    "        # 数据整理\n",
    "        shapes = make_shapes(shapes)\n",
    "        # 检验非法积木\n",
    "        if not valid_shapes(shapes):\n",
    "            return False\n",
    "        # 存储积木\n",
    "        areas = []\n",
    "        for shape in shapes:\n",
    "            area = Area(shape)\n",
    "            areas.append(area)\n",
    "        # 判断积木之间的合法性\n",
    "        if not valid_areas(areas):\n",
    "            return False\n",
    "        # 计算每两块积木之间的拼接可能性\n",
    "        merge_valids = calc_merge_valids(areas)\n",
    "        # 每块积木的每条边至少有一个可以和别人拼\n",
    "        if not valid_merge_valids(merge_valids):\n",
    "            return False\n",
    "        # 判断能否成功\n",
    "        mng = Manager(merge_valids)\n",
    "        if not mng.merge_all():\n",
    "            return False\n",
    "        return True\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def composeCube(self, shapes: List[List[str]]) -> bool:\r\n",
    "        def cal(shape):\r\n",
    "            res = [0]*48\r\n",
    "            for i, j in product(range(n), range(n)):\r\n",
    "                if shape[i][j] == '0':\r\n",
    "                    continue\r\n",
    "                for turn, (i2, j2) in enumerate([(i, j), (i, n-1-j)]):\r\n",
    "                    for rotate, (x, y) in enumerate([(i2, j2), (j2, n-1-i2), (n-1-i2, n-1-j2), (n-1-j2, i2)]):\r\n",
    "                        for side, (x2, y2, z2) in enumerate([(x, y, 0), (x, y, n-1), (0, y, x), (n-1, y, x), (x, 0, y), (x, n-1, y)]):\r\n",
    "                            res[turn*24+rotate*6+side] |= 1<<(x2*n*n+y2*n+z2)\r\n",
    "            return res\r\n",
    "    \r\n",
    "        n = len(shapes[0])\r\n",
    "        if sum(''.join(shape).count('1') for shape in shapes) != 2*n*n+4*(n-1)*(n-2):\r\n",
    "            return False\r\n",
    "        dp = {0}\r\n",
    "        for i in range(6):\r\n",
    "            dp = {st|st2 for st in cal(shapes[i]) for st2 in dp if not st&st2}\r\n",
    "        return bool(dp)"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
